package org.hfy.collections;

import dnl.utils.text.table.TextTable;
import org.hfy.Constants;
import org.hfy.collections.helper.*;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @Description:
 * @Author: Takagi
 * @date: 2023/5/6
 */
public class LRAutomaton implements LRPredictUtil {
    // 开始符号
    public Symbol start;
    // 文法产生式
    public List<Production> productions;
    // 非终结符列表
    public List<NonTerminator> nonTerminatorList;
    // 拓广文法的产生式
    public Production extendGrammarProduction;

    /*
     * @Author Takagi
     * @Description: 获取产生式编号
     * @date: 2023/5/13
     * @param production
     * @return * @return int
     **/
    public int indexOfProduction(Production production) {
        return this.productions.indexOf(production);
    }

    /*
     * @Author Takagi
     * @Description: 设定文法开始符号
     * @date: 2023/5/13
     * @param start
     * @return
     **/
    public void setStart(Symbol start) {
        this.start = start;
    }

    /*
     * @Author Takagi
     * @Description: 初始化
     * @date: 2023/4/23
     * @Param start 文法的开始符号
     * @param productions 文法的产生式
     * @return
     **/
    public void init(Symbol start, List<Production> productions) {
        this.nonTerminatorList = new LinkedList<>();
        this.setStart(start);
        this.setProductions(productions);
        this.extendGrammar();
        this.parseProductions();
        this.solveFirstSet();
        this.solveFollowSet();
    }


    /*
     * @Author Takagi
     * @Description: 解析产生式
     * @date: 2023/4/23
     * @Param
     * @return
     **/
    public void parseProductions() {
        if (this.productions.size() > 0) {
            for (Production production : this.productions) {
                Symbol left = production.left;
                SymbolString right = production.right;
                int idx = this.nonTerminatorList.indexOf(new NonTerminator(left));
                // 解析过的非终结符，将产生式右侧添加到 equal list
                if (idx != -1) {
                    NonTerminator nonTerminator = this.nonTerminatorList.get(idx);
                    nonTerminator.equalList.add(right);
                } else {
                    NonTerminator nonTerminator = new NonTerminator(left);
                    nonTerminator.equalList.add(right);
                    this.nonTerminatorList.add(nonTerminator);
                }
            }
        }
    }

    /*
     * @Author Takagi
     * @Description: 拓广文法
     * @date: 2023/4/23
     * @Param
     * @return
     **/
    public void extendGrammar() {
        NonTerminator nonTerminator = new NonTerminator(new Symbol(this.start.getContent() + Constants.SYMBOL_ALIAS));
        nonTerminator.equalList.add(new SymbolString(this.start.getContent()));
        LinkedList<NonTerminator> nonTerminatorList = (LinkedList<NonTerminator>) this.nonTerminatorList;
        this.extendGrammarProduction = new Production(nonTerminator.name, nonTerminator.getFirstEqual());
        nonTerminatorList.addFirst(nonTerminator);
    }

    /*
     * @Author Takagi
     * @Description: 获取文法的所有符号
     * @date: 2023/4/26
     * @param
     * @return * @return Set<Symbol>
     **/
    public Set<Symbol> getAllSymbols() {
        Set<Symbol> allSymbols = new HashSet<>();
        for (Production production : this.productions) {
            allSymbols.add(production.left);
            allSymbols.addAll(production.right.symbolList);
        }
        return allSymbols;
    }

    /*
     * @Author Takagi
     * @Description: 打印非终结符
     * @date: 2023/4/23
     * @Param
     * @return
     **/
    public void showNonTerminatorList() {
        for (NonTerminator nonTerminator : this.nonTerminatorList) {
            System.out.printf(
                    "%s :\nEqual List : %s\nFirst : %s\nFollow : %s\n\n",
                    nonTerminator.name.content,
                    nonTerminator.equalList.toString(),
                    nonTerminator.First.toString(),
                    nonTerminator.Follow.toString()
            );
        }
    }

    /*
     * @Author Takagi
     * @Description: 打印产生式
     * @date: 2023/4/23
     * @Param
     * @return
     **/
    public void showProductions() {
        for (Production production : this.productions) {
            System.out.println(production);
        }
        System.out.print(Constants.END);
    }

    /*
     * @Author Takagi
     * @Description: 根据 name 查找非终结符
     * @date: 2023/4/23
     * @param name
     * @return * @return NonTerminator
     **/
    public NonTerminator getNonTerminatorByName(Symbol name) {
        for (NonTerminator nonTerminator : this.nonTerminatorList) {
            if (nonTerminator.name.equals(name)) {
                return nonTerminator;
            }
        }
        return null;
    }

    /*
     * @Author Takagi
     * @Description: 递归求解非终结符的 First 集合
     * @date: 2023/4/23
     * @param nonTerminator
     * @return * @return Set<Symbol>
     **/
    private Set<Symbol> getFirstSet(NonTerminator nonTerminator) {
        Set<Symbol> firstSet = new HashSet<>();
        for (SymbolString symbolString : nonTerminator.equalList) {
            Symbol firstSymbol = symbolString.getFirstSymbol();
            if (firstSymbol.equals(nonTerminator.name)) continue;
            if (Constants.isTerminator(firstSymbol) || Constants.isEpsilon(firstSymbol)) {
                firstSet.add(firstSymbol);
            } else {
                NonTerminator nextNonTerminator = this.getNonTerminatorByName(firstSymbol);
                if (nextNonTerminator != null) {
                    firstSet.addAll(getFirstSet(nextNonTerminator));
                }
            }
        }
        return firstSet;
    }

    /*
     * @Author Takagi
     * @Description: 求出所有非终结符的 First 集合
     * @date: 2023/4/23
     * @param
     * @return
     **/
    public void solveFirstSet() {
        for (NonTerminator nonTerminator : this.nonTerminatorList) {
            nonTerminator.First = getFirstSet(nonTerminator);
        }
    }

    /*
     * @Author Takagi
     * @Description: 求出所有非终结符的 Follow 集合
     * @date: 2023/4/25
     * @param
     * @return
     **/
    public void solveFollowSet() {
        while (true) {
            boolean makeChange = false;
            for (NonTerminator nonTerminator : this.nonTerminatorList) {
                // 1. 产生式左侧非终结符添加文本结束符
                makeChange |= nonTerminator.updateFollowSet(new Symbol(Constants.EOF));

                for (SymbolString symbolString : nonTerminator.equalList) {
                    // 产生式右侧的最后一个符号
                    Symbol lastSymbol = symbolString.getLastSymbol();
                    NonTerminator lastNonTerminator = this.getNonTerminatorByName(lastSymbol);

                    // 产生式右侧的倒数第二个符号
                    Symbol penultimateSymbol = symbolString.getPenultimateSymbol();
                    NonTerminator penultimateNonTerminator = this.getNonTerminatorByName(penultimateSymbol);

                    // 2. Follow(产生式左侧) 添加到 Follow(产生式末尾的非终结符)
                    if (Constants.isNonTerminator(lastSymbol)) {
                        makeChange |= lastNonTerminator.updateFollowSet(nonTerminator.Follow);

                        if (Constants.isNonTerminator(penultimateSymbol)) {
                            // 3. S -> AB，B 可以推出 epsilon，将 Follow(S) 添加到 Follow(A)
                            if (lastNonTerminator.canDeriveEpsilon()) {
                                makeChange |= penultimateNonTerminator.updateFollowSet(nonTerminator.Follow);
                            }

                            // 4. 将 First(B) 加入 Follow(A)
                            makeChange |= penultimateNonTerminator.updateFollowSet(lastNonTerminator.First);
                        }
                    }

                    // 5. 产生式右侧中，非终结符右侧出现终结符
                    for (int i = 0; i < symbolString.symbolList.size() - 1; ++i) {
                        Symbol symbol = symbolString.symbolList.get(i);
                        Symbol nextSymbol = symbolString.symbolList.get(i + 1);
                        if (Constants.isNonTerminator(symbol) && Constants.isTerminator(nextSymbol)) {
                            makeChange |= this.getNonTerminatorByName(symbol).updateFollowSet(nextSymbol);
                        }
                    }
                }
            }
            if (!makeChange) break;
        }
    }

    /*
     * @Author Takagi
     * @Description: 读取产生式
     * @date: 2023/4/23
     * @Param * @param productions
     * @return
     **/
    public void setProductions(List<Production> productions) {
        this.productions = productions;
    }

    /*
     * @Author Takagi
     * @Description: 求解项目集闭包
     * @date: 2023/5/14
     * @param itemSet
     * @return * @return Set<Production>
     **/
    @Override
    public Set<Production> getItemSetClosure(ItemSet itemSet) {
        return null;
    }

    /*
     * @Author Takagi
     * @Description: 获取初始项目集合
     * @date: 2023/5/14
     * @param
     * @return * @return ItemSet
     **/
    @Override
    public ItemSet getInitialItemSet() {
        return null;
    }

    /*
     * @Author Takagi
     * @Description: 处理状态转移
     * @date: 2023/5/20
     * @param name
     * @param itemSet
     * @param itemSetFamily
     * @return * @return State
     **/
    public State solveState(int name, ItemSet itemSet, List<ItemSet> itemSetFamily) {
        return null;
    }

    /*
     * @Author Takagi
     * @Description: 打印预测分析表
     * @date: 2023/5/13
     * @param table
     * @param data
     * @param allSymbol
     * @return
     **/
    public void showPredictTable(LRPredictTable table, List<List<String>> data, Set<Symbol> allSymbol) {
        List<String> header = table.getTableHeader(allSymbol);
        TextTable textTable = new TextTable(header.toArray(new String[0]), data.stream()
                .map(l -> l.toArray(new String[0]))
                .toArray(String[][]::new));
        textTable.printTable();
        System.out.println(Constants.END);
    }

    /*
     * @Author Takagi
     * @Description: 获取项目集合在项目集规范族中的索引
     * @date: 2023/5/13
     * @param itemSetFamily
     * @param itemSet
     * @return * @return int
     **/
    public int indexOfItemSet(List<ItemSet> itemSetFamily, ItemSet itemSet) {
        List<Set<Production>> a = itemSetFamily.stream().map(ItemSet::getAllItemIgnoreLRFlag).collect(Collectors.toList());
        Set<Production> b = itemSet.getAllItemIgnoreLRFlag();
        return a.indexOf(b);
    }

    /*
     * @Author Takagi
     * @Description: 构建 LR 分析表
     * @date: 2023/5/13
     * @param
     * @return * @return LRPredictTable
     **/
    public LRPredictTable constructLrPredictTable() {
        LRPredictTable table = new LRPredictTable();
        List<ItemSet> itemSetFamily = solveItemSetFamily();

        // 打印信息
        Set<Symbol> allSymbol = getAllSymbols();
        allSymbol.add(new Symbol(Constants.EOF));
        List<List<String>> data = new LinkedList<>();

        for (int i = 0; i < itemSetFamily.size(); ++i) {
            ItemSet itemSet = itemSetFamily.get(i);
            State state = solveState(i, itemSet, itemSetFamily);
            table.addStateName(state.getName());
            table.setState(state.name, state);
            data.add(state.getStateString(allSymbol));
        }
        showPredictTable(table, data, allSymbol);
        return table;
    }

    /*
     * @Author Takagi
     * @Description: LR 预测分析
     * @date: 2023/5/13
     * @param inputString
     * @return
     **/
    public void LrPredict(SymbolString inputString) {
        inputString.addSymbol(new Symbol(Constants.EOF));
        LRPredictTable LRPredictTable = this.constructLrPredictTable();
        Stack<Symbol> stack = new Stack<>();
        Queue<Symbol> queue = new LinkedList<>(inputString.symbolList);

        String[] header = {"stack", "input", "action"};
        List<List<String>> data = new LinkedList<>();
        stack.add(LRPredictTable.getFirstState().name);
        while (true) {
            List<String> line = new LinkedList<>();
            line.add(stack.toString());
            line.add(queue.toString());
            Symbol stateName = stack.peek();
            Symbol front = queue.peek();
            State state = LRPredictTable.getState(stateName);
            Action action = state.getAction(front);
            if (action == null) {
                line.add(Constants.REJECT);
                data.add(line);
                break;
            } else if (action.accept) {
                line.add(Constants.ACCEPT);
                data.add(line);
                break;
            } else {
                // 移进状态
                if (Constants.isShiftAction(action.actionType)) {
                    stack.add(front);
                    stack.add(action.stateNo);
                    line.add(Constants.SHIFT_ACTION);
                    queue.poll();
                } else {
                    // 归约状态
                    int size = 2 * action.production.getProductionIgnoreItem().right.size();
                    // 移除栈中 2 倍的产生式右侧符号数量
                    while (size-- > 0) stack.pop();
                    State topState = LRPredictTable.getState(stack.peek());
                    Symbol left = action.production.left;
                    stack.add(left);
                    // 对非终结符进行转移
                    if (topState.getGoto(left) == null) {
                        line.add(Constants.REJECT);
                        data.add(line);
                        break;
                    } else {
                        stack.add(topState.getGoto(left));
                        line.add(action.production.getProductionIgnoreItem().toString());
                    }
                }
            }
            data.add(line);
        }

        // 打印预测过程
        TextTable textTable = new TextTable(header, data.stream()
                .map(l -> l.toArray(new String[0]))
                .toArray(String[][]::new));
        textTable.printTable();
    }

    /*
     * @Author Takagi
     * @Description: 项目集输入 input 得到的新项目集
     * @date: 2023/5/13
     * @param itemSet
     * @param input
     * @return * @return ItemSet
     **/
    public ItemSet move(ItemSet itemSet, Symbol input) {
        ItemSet res = new ItemSet();
        for (Production production : itemSet.getAllItem()) {
            if (production.getItemNextSymbol().equals(input)) {
                Production next = production.getNextItem();
                if (next != null) {
                    res.addCoreItem(next);
                }
            }
        }
        if (res.getCoreItemSize() == 0) return null;
        res.nonCoreItemSet = getItemSetClosure(res);
        return res;
    }

    /*
     * @Author Takagi
     * @Description: 求解项目集规范族
     * @date: 2023/5/13
     * @param
     * @return * @return List<ItemSet>
     **/
    public List<ItemSet> solveItemSetFamily() {
        ItemSet initialItemSet = this.getInitialItemSet();
        List<ItemSet> res = new LinkedList<>();
        Queue<ItemSet> queue = new LinkedList<>();
        res.add(initialItemSet);
        queue.add(initialItemSet);
        while (queue.size() > 0) {
            ItemSet front = queue.poll();
            List<Symbol> inputs = new LinkedList<>(front.getInputSymbols());
            Collections.reverse(inputs);
            for (Symbol input : inputs) {
                ItemSet output = move(front, input);
                if (output != null && !res.contains(output)) {
                    res.add(output);
                    queue.add(output);
                }
            }
        }
        return res;
    }

    public void showItemSetFamily() {
        List<ItemSet> itemSetFamily = solveItemSetFamily();
        for (int i = 0; i < itemSetFamily.size(); i++) {
            System.out.printf("I%d\n", i);
            ItemSet itemSet = itemSetFamily.get(i);
            Set<Production> allItem = itemSet.getAllItem();
            for (Production production : allItem) {
                System.out.println(production);
            }
            System.out.println("\n");
        }
    }
}
